1. Technical Field
This invention generally relates to storage and retrieval of electronic entities. More particularly, this invention relates to automatically changing the data structure of a storage and retrieval system based on the detection of conditions indicating that a different structure would provide improved performance.
2. Related Art
Some data storage and retrieval mechanisms use lookup keys to store and identify data. Such mechanisms include caches, associative arrays, and databases. The keys are associated with the corresponding data according to a specific internal data structure. These internal data structures may, for example, comprise trees, hashes, heaps, and lists. Each of these data structures enables the storage of data in a different manner and therefore provides different performance characteristics. Some of these data structures are described briefly below.
A list is simply an unordered set (a list) that enumerates all of the keys and corresponding data. A hash is an associative array in which a key is converted to a hash table entry. The hash table entry defines the position in a hash table in which the corresponding data is stored. The hash table is static and may be only partially filled. A tree is a hierarchical data structure in which keys and their associated data are stored in a sorted manner. A heap is a tree which is only partially sorted. Hybrid structures may combine, for instance, a first layer of trees or heaps with a second layer of hashes or lists.
Different data structures are optimal for different uses. Consequently, the selection of a data structure for use in a particular application typically depends upon the manner in which the data is expected to be used, as well as the amount of the data to be stored, and the type of access to the data that will be needed. The greater particularity with which these factors can be specified, the more accurately a developer can select an “optimal” data structure for the application.
It is therefore apparent that one of the problems with selecting a data structure that will provide the best performance in an application is identifying the conditions under which the data structure will be used. While it may be relatively easy to identify factors such as the type of data that will be stored and the types of access that will be needed, it is typically much more difficult to identify things like the frequency of accesses, or any patterns with which the accesses are made.
As a result of the difficulty in predicting some of the factors which form the basis for determining which data structure is “optimal,” a software developer may simply have to make an educated guess as to which type of data structure will ultimately provide the best performance. This guess may turn out to be accurate, or it may not. If the developer has selected a data structure that is not actually optimal, the performance of the application may be substantially degraded by the less-than-optimal performance of the selected data structure.